package Testdemo2;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:周次煜
 * Date: 2024-05-08
 * Time：12:50
 */
public class Test8 {
    public static int[] searchRange(int[] nums, int target) {

        // 定义一个存放起始和终止位置的数组
        int[] ret=new int[]{-1,-1};

        // 得到长度
        int len=nums.length;


        // 进行二分操作
        // 定义左右指针
        int left=0,right= len-1;

        /**
         * 寻找右边界
         *
         *  当 right = mid = left 就会陷入死循环
         *  细节一 : 循环终止条件 ： 这里不可以进行 取等
         *
         *  当 中点值 >= target  时 进行 right 移动
         *  细节二 : 右指针 right 移动的位置 是 到达  中点下标 mid
         *
         *
         *  left  mid  right
         *  当 中点 和 left  right 相邻 时就需要
         *  细节三 : 确立 mid = left +(  (right - left ) >>> 1 )
         */
        //
        while(left < right) {
            int mid=left + ( (right-left) >>> 1);
            if(nums[mid] < target) {
                left = mid+1;
            }  else if(nums[mid] >= target) {
                right = mid ;
            }
        }

        if(nums[right] == target) ret[0] = right;

        left=0;
        right=len-1;

        /**
         * 寻找左边界
         * 当 right = mid = left 就会陷入死循环
         * 细节一 : 终止条件 不能写等号
         *
         * 当 中点值  <= target 时
         * 细节二 ： 我们更新 left = mid
         *
         * 当 left  mid  right  相邻 时
         *  细节三 ： 更新 mid = left + ( (right - left + 1) >>> 1 )
         *
         */
        while(left < right) {
            int flg=left + ( (right - left + 1) >>> 1);
            if(nums[flg] <= target) {
                left = flg;
            }  else if(nums[flg] > target) {
                right = flg -1;
            }
        }

        if (nums[left]== target) ret[1]= left;
        return ret;
    }

    public static void main7(String[] args) {
        int []array={5,7,7,8,8,10};
        System.out.println(Arrays.toString(searchRange(array, 8)));
    }

    /**
     * 求 x 的算数平方根
     *
     * 利用在前面的数值的平方 小于等于 x
     * 故所以我们求    <= 的右边界
     * @param x 目标值
     * @return 返回该值的 算术平方根
     */

    public static long mySqrt(int x) {
        if(x < 1) return 0;


        // 寻找 <= 的右边界
        long left=0,right = x;
        while(left < right) {
            // 得到 中间下标 需要 +1
            long mid= left + (   ( right - left + 1) >>> 1 );
            if( (mid * mid ) > x) {
                // 当中间值 右边界 的右边 就 -1 向左移动
                right=mid-1;
            } else {
                // 而在左边时，一定注意 mid 有可能是右边界
                left=mid;
            }
        }

        // 返回相遇值
        return right;
    }

    public static void main(String[] args) {
        System.out.println(mySqrt(2147395599));
    }

    /**
     * 山脉数组的封顶索引
     *  利用
     *  在山顶左边 这个数 大于 前一个数
     *  在山顶 右边 这个数 小于前一个数的二层性
     *  <= 的右边界
     *  进行二分查找
     * @param arr 该山脉的数组
     * @return 返回山顶值
     */

    public int peakIndexInMountainArray(int[] arr) {
        // 得到数组长度
        int sz= arr.length;

        // 进行 左二分查找算法
        int left=0,right=sz-1;
        while(left < right) {
            // 根据下面是否 -1 判断是否 +1
            int mid= left+ ((right -left +1) >>> 1);

            // 当这个数大于 前一个数
            if(arr[mid] >= arr[mid-1]) {
                // 处于山峰左边就小于等于中点值，有可能成为右边界
                left=mid;
            } else {
                // 处于山峰右边 就左移到 中点值-1
                right= mid -1;
            }
        }
        return left;
    }


    /**
     * 寻找 右旋数字后的最小值
     * 有端点的这个是最终我们右旋后得到的连接的
     * 以这个值为基准
     * 我们确立了两个不等关系
     * 右旋的过去的那些数字 都 大于 这个基准值，也就在最小值的左边
     * 未右旋的那些数字 ， 在 最小值的右边 而且是  同样是 <= 我们的基准值
     *
     **/


    public int findMin(int[] nums) {
        // 进行二分左查找
        int left= 0, right=nums.length-1;

        // 以 最右边为基准值 进行 原数组的划分
        int flg=nums[right];

        // 二分查找的   <=  的左边界

        while(left < right) {

            // 得到中间 下标
            int mid= left + (  (right - left ) >>> 1 );

            // 如果 大于 基准   说明 是 左边的数 ， 不存在最小值
            if( nums[mid]  >  flg) {
                left = mid +1;
            } else {
                // 存在 右边 小于或等于 基准值
                // 就有可能是 我们要求的最小值
                right =mid;
            }
        }


        return nums[left];
    }

    /**
     * 寻找峰值
     *
     *  在山顶左边 这个数 大于 前一个数
     *  在山顶 右边 这个数 小于前一个数的二层性
     *  <= 的右边界
     *  进行二分查找
     * @param nums 该山脉的数组
     * @return 返回山顶值
     */

    public int findPeakElement(int[] nums) {
        // 进行 左二分查找算法
        int left=0,right=nums.length-1;

        while(left < right) {
            int mid= left +  ( (right - left + 1) >>> 1 );
            if(nums[mid] > nums[mid-1]) {
                left = mid;
            } else {
                right = mid -1;
            }
        }

        return right;
    }


    /**
     * 查找缺失的数字
     * @param records 含有缺失数字的数组
     * @return 返回缺失的 数字
     */


    /**
     *  方法一 :  二分查找法
     * 利用 等于下标值 和 不等于下标值
     * 划分 左右区间
     * 右边界的左边
     *
     */
    public int takeAttendance1(int[] records) {

        // 二分算法求点名人数
        int left=0,right= records.length-1;


        while(left < right) {
            int mid = left + ( (right - left) >>> 1);

            // 只要 下标值 等于 元素 就说明在左边
            if(records[mid] == mid) {
                // 需要一直往右移
                left = mid +1;
            } else {
                // 当下标值 ！等于该元素 说明 在右边（包括缺失的值）
                right = mid;
            }
        }

        // 细节处理特殊情况
        // 当我们的最终的下标得到的是缺失的值
        // 还需要判断是否在数组内部
        if(records[right] == right) return right+1;


        return right;

    }


    /**
     * 方法二： 用哈希表实现
     *
     * 先统计 每个数字出现的个数
     * 然后再排查没有出现的数字就是我们缺失的数字
     *
     */

    //
    public int takeAttendance2(int[] records) {

        // 建立一个数组 length+1 的数组
        int []array = new int[records.length+1];

        // 用哈希表 统计 出现的数字的个数
        for(int i = 0 ; i < records.length ; i++) {
            array[records[i]]++;
        }

        // 进行数据的排查
        for(int j = 0 ; j < array.length ; j++) {
            // 一旦出现 = 0 的数字下标就返回
            if(array[j]==0) return j;
        }

        // 特殊情况时
        // 就返回 该数组最后边界
        return records.length;
    }


    /**
     *  方法三： 直接遍历判断
     *
     *  只要出现不等于下标的元素
     *  返回的该下标就就是我们缺失的元素
     *
     */

    public int takeAttendance3(int[] records) {
        // 直接遍历找结果
        for(int i=0; i< records.length; i++) {
            if(records[i] != i) return i;
        }

        // 特殊情况
        // 有可能是数组外的那个元素
        // 就返回 长度的下标
        return records.length;
    }

    /**
     *  方法四 ： 位运算
     *
     * 利用和按位异或的特性
     *  将每个数字进行按位异或
     *  只要再和每个 对应数字进行
     *  最终缺失的那个就是我们的值
     *
     */

    public int takeAttendance4(int[] records) {

        int flg=0;
        // 位运算
        for(int i = 1 ; i < records.length + 1; i++) {

            // 将数组每个元素进行按位异或
            flg ^=  records[i-1];

            // 再将 对应下标进行异或
            flg ^= i;

        }

        // 最终返回下标值
        return flg;

    }


    /**
     *  方法五 ： 高斯求和公式
     *  利用等差数列的求和公式
     *  计算得到的总和 在逐个减去 数组每个元素
     *  最终剩余的值就是我们缺失的值
     */


    class Solution {
        public int takeAttendance(int[] records) {


            int sum=0;

            // 利用 高斯 求和公式

            // 第一步先利用等差数列求和公式 计算出总和
            sum= ( records.length  * (records.length + 1) ) / 2;
            for(int i = 0 ; i < records.length ; i++) {
                // 将计算的总和 减去 数组中的值
                // 多出来的就是我们减少的值
                sum -= records[i];
            }


            return sum;
        }
    }
}
